package model;

import org.tinylog.Logger;

import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class SlidingBox {
    /**
     * 盒中的所有滑块
     * key为滑块的编号，value为此编号下的滑块列表
     */
    private Map<Character, List<Block>> blocks;
    /**
     * 空白滑块列表，编码为0
     */
    private List<Block> emptyBlocks;
    /**
     * 主滑块列表，编码为1
     */
    private Block primaryBlock;
    /**
     * 上一状态
     */
    private SlidingBox prevSlidingBox;
    /**
     * 从出发状态到达此状态的最少步数
     */
    private int steps;
    /**
     * 下一步所有可能状态的缓存
     */
    private List<SlidingBox> nextSteps;
    /**
     * 此盒的字符串表示
     */
    private String stateString;
    /**
     * 初始数据
     */
    private char[][] data;
    /**
     * 利用关卡数据构造滑块盒
     */
    public SlidingBox() {
        this.prevSlidingBox = null;
        this.primaryBlock = null;
        this.emptyBlocks = new ArrayList<>();
        this.blocks = new HashMap<>();
        this.prevSlidingBox = null;
        this.nextSteps = null;
        this.steps = Integer.MAX_VALUE;
        this.stateString = "";
    }

    public Map<Character, List<Block>> getBlocks() {
        return blocks;
    }

    public int getSteps() {
        return steps;
    }

    public void setSteps(int steps) {
        this.steps = steps;
    }

    /**
     * 获取下一步可能得到的所有状态
     *
     * @return 所有可能得到的下一状态
     */
    public List<SlidingBox> getNextSteps() {
        //避免重复计算所有下一步状态
        if (this.nextSteps != null) {
            return this.nextSteps;
        }
        List<SlidingBox> nextResults = new ArrayList<>();
        //本状态如果在之前出现过，就不做任何移动直接返回
        if (this.duplicatesSelf()) {
            this.nextSteps = nextResults;
            return nextResults;
        } else {
            //对空白滑块尝试移动
            for (Block emptyBlock : this.emptyBlocks) {
                //找到空白滑块的所有邻居
                List<Block> blockNeighbours = this.findBlockNeighbours(emptyBlock);
                //对每个邻居滑块逐一尝试移动到此空白位置
                for (Block neighbourBlock : blockNeighbours) {
                    //如果邻居是实体滑块
                    if (neighbourBlock.getCode() != '0') {
                        //移动此邻居滑块到空白位置，把尝试结果加入下一步状态集中，注意，尝试的结果可能为null
                        nextResults.add(this.moveToNext(neighbourBlock, emptyBlock));
                    } else {
                        //合并两个空滑块为1个
                        Block combinedEmptyBlock = new Block(emptyBlock.getCells().get(0));
                        combinedEmptyBlock.getCells().add(neighbourBlock.getCells().get(0));
                        //找到这个复合滑块的复合邻居，进行复合移动
                        //比如，两个横向相邻的空白滑块。上方有两个相邻的2行1列滑块
                        List<Block> mergedNeighbourBlocks = this.mergeNeighbourBlocks(
                                this.findBlockNeighbours(combinedEmptyBlock),
                                combinedEmptyBlock);
                        for (Block mergedNeighbourBlock : mergedNeighbourBlocks) {
                            //用合并空滑块形成的新空滑块再尝试移动
                            nextResults.add(this.moveToNext(mergedNeighbourBlock, combinedEmptyBlock));
                        }
                    }
                }
            }
        }

        //去空去重，留下可行的状态再返回
        //回环检测也放到这里
        //延迟加载
        this.nextSteps = nextResults.stream()
                .filter(Objects::nonNull)
                .distinct()
                .filter(slidingBox -> !slidingBox.duplicatesSelf())
                .collect(Collectors.toList());
        return this.nextSteps;
    }

    /**
     * 判断此状态在之前有无出现过
     * 一直查找之前的状态进行比对，如果有相同状态，说明此状态在之前已经尝试过
     *
     * @return 有出现过则返回true，否则返回false
     */
    public boolean duplicatesSelf() {
        SlidingBox prev = this.prevSlidingBox;
        while (prev != null) {
            if (prev.equals(this)) {
                return true;
            }
            prev = prev.getPrevSlidingBox();
        }
        return false;
    }

    /**
     * 查找相邻的滑块
     * 1.获取此滑块的所有网格
     * 2.获取每个网格的所有相邻网格，并去掉重复的，以及属于滑块内部的网格
     * 3.获取每个网格所属的滑块
     * 4.对获取的滑块去重，得到结果
     *
     * @param block 基准滑块
     *
     * @return 找到的滑块邻居
     */
    private List<Block> findBlockNeighbours(Block block) {
        return block.getCells().stream()
                //获取该网格的相邻网格
                .flatMap((Function<Cell, Stream<Cell>>) cell -> this.getCellNeighbours(cell).stream())
                //相邻网格去重
                .distinct()
                //再去掉包含在滑块内的网格
                //这里用contains没有坑，因为网格的位置是唯一的，但是box就不行，因为不同的box实例可能有相同的state
                .filter(cell -> !(block.getCells().contains(cell)))
                //利用网格查找所在滑块，去重去空
                .map(cell -> this.findBlock(cell.getRow(), cell.getCol()))
                .filter(Objects::nonNull)
                .distinct()
                .collect(Collectors.toList());
    }

    /**
     * 移动滑块到指定位置，从而产生下一状态
     *
     * @param solidBlock 要移动的实体滑块
     * @param emptyBlock 移动到的空白滑块
     *
     * @return 下一状态的滑块盒，如果不可移动，则返回null
     */
    private SlidingBox moveToNext(Block solidBlock, Block emptyBlock) {
        SlidingBox nextSlidingBox;
        //要求from为实滑块，to为空白滑块，否则不可移动
        if (!((solidBlock.getCode() != '0') && (emptyBlock.getCode() == '0'))) {
            return null;
        }
        //获取起点与终点滑块的范围
        int[] solidRange = solidBlock.getRange(),
                emptyRange = emptyBlock.getRange();
        int solid_x_left = solidRange[0],
                solid_x_right = solidRange[2],
                solid_y_up = solidRange[1],
                solid_y_down = solidRange[3];
        int empty_x_left = emptyRange[0],
                empty_x_right = emptyRange[2],
                empty_y_up = emptyRange[1],
                empty_y_down = emptyRange[3];

        //列范围相同说明在竖直方向对齐，可以移动
        if (solid_x_left == empty_x_left && solid_x_right == empty_x_right) {
            //实心块要移动的距离是空白块的高度，空白块要移动的距离是实心块的高度
            int solidHeight = solid_y_down - solid_y_up + 1,
                    emptyHeight = empty_y_down - empty_y_up + 1;
            //empty在solid下方为1，反之为-1
            int factor = (empty_y_up > solid_y_down) ? 1 : -1;
            int y_to_empty = emptyHeight * factor,
                    y_to_solid = solidHeight * factor;
            //修改盒中滑块的位置，纵向移动实滑块,空白块往反方向移动
            solidBlock.getCells().forEach(cell -> cell.setRow(cell.getRow() + y_to_empty));
            emptyBlock.getCells().forEach(cell -> cell.setRow(cell.getRow() - y_to_solid));
            //构造下一状态的滑块盒
            nextSlidingBox = nextBoxFromCurrent();
            //构造下一状态后，把滑块恢复原位
            solidBlock.getCells().forEach(cell -> cell.setRow(cell.getRow() - y_to_empty));
            emptyBlock.getCells().forEach(cell -> cell.setRow(cell.getRow() + y_to_solid));

        }
        //行范围相同，说明横向对齐，可移动
        else if (solid_y_up == empty_y_up && solid_y_down == empty_y_down) {
            //行范围相同可进行横向移动
            int solidWidth = solid_x_right - solid_x_left + 1,
                    emptyWidth = empty_x_right - empty_x_left + 1;
            //空滑块在右边为正，否则为负
            int factor = empty_x_left > solid_x_right ? 1 : -1;
            int deltaX1 = emptyWidth * factor,
                    deltaX2 = solidWidth * factor;
            solidBlock.getCells().forEach(cell -> cell.setCol(cell.getCol() + deltaX1));
            emptyBlock.getCells().forEach(cell -> cell.setCol(cell.getCol() - deltaX2));
            //构造下一状态的滑块盒
            nextSlidingBox = nextBoxFromCurrent();
            solidBlock.getCells().forEach(cell -> cell.setCol(cell.getCol() - deltaX1));
            emptyBlock.getCells().forEach(cell -> cell.setCol(cell.getCol() + deltaX2));
            //滑块不对齐，不可移动
        } else {
            return null;
        }

        return nextSlidingBox;
    }

    /**
     * 把相邻滑块按照相对于中心滑块的位置分类
     *
     * @param neighbourBlocks 搜索到的周边滑块
     * @param centralBlock    复合空滑块
     *
     * @return 合并后的滑块列
     */
    private List<Block> mergeNeighbourBlocks(List<Block> neighbourBlocks, Block centralBlock) {
        //滑块垃圾分类投放到四个桶里
        List<Block> up = new ArrayList<>(),
                down = new ArrayList<>(),
                left = new ArrayList<>(),
                right = new ArrayList<>();
        //获得中心滑块的范围
        int[] centralRange = centralBlock.getRange();
        int central_left = centralRange[0], central_right = centralRange[2],
                central_up = centralRange[1], central_down = centralRange[3];
        //逐个检查相邻滑块并取得范围，用于判断相对于中心滑块的位置
        //只需要占据了滑块一整边的邻居滑块
        //忽略某一边存在两个滑块的情形
        for (Block neighbourBlock : neighbourBlocks) {
            int[] neighbourRange = neighbourBlock.getRange();
            int neighbour_left = neighbourRange[0], neighbour_right = neighbourRange[2],
                    neighbour_up = neighbourRange[1], neighbour_down = neighbourRange[3];
            //上方滑块
            if (neighbour_down < central_up) {
                up.add(neighbourBlock);
            }
            //下方滑块
            else if (neighbour_up > central_down) {
                down.add(neighbourBlock);
            }
            //左方滑块
            else if (neighbour_right < central_left) {
                left.add(neighbourBlock);
            }//右方滑块
            else if (neighbour_left > central_right) {
                right.add(neighbourBlock);
            }
        }
        //取出长度为1的列表中的元素，再汇集成一个列表
        return Stream.of(up, down, left, right)
                .filter(list -> list.size() == 1)
                .flatMap(Collection::stream)
                .distinct()
                .collect(Collectors.toList());
    }

    public SlidingBox getPrevSlidingBox() {
        return prevSlidingBox;
    }

    public void setPrevSlidingBox(SlidingBox prevSlidingBox) {
        this.prevSlidingBox = prevSlidingBox;
    }

    /**
     * 获取网格的4个邻居
     *
     * @param cell 基准网格
     *
     * @return 四个方向的邻居网格，依次为上,下，左，右
     */
    private List<Cell> getCellNeighbours(Cell cell) {
        List<Cell> neighbours = new ArrayList<>();
        int row = cell.getRow(), col = cell.getCol();
        //四个方向的邻居网格，依次为上,下，左，右
        neighbours.add(this.findCell(row - 1, col));
        neighbours.add(this.findCell(row + 1, col));
        neighbours.add(this.findCell(row, col - 1));
        neighbours.add(this.findCell(row, col + 1));
        //去掉null元素
        neighbours.removeIf(Objects::isNull);
        return neighbours;
    }

    /**
     * 根据位置查找滑块
     *
     * @param row 行号
     * @param col 列号
     *
     * @return 查找到的滑块
     */
    private Block findBlock(int row, int col) {
        final Block[] resultBlock = new Block[1];
        this.blocks.forEach((code, blockList) -> blockList.forEach(block -> block.getCells().forEach(cell -> {
            if (cell.getRow() == row && cell.getCol() == col) {
                resultBlock[0] = block;
            }
        })));
        return resultBlock[0];
    }

    /**
     * 把当前的滑块状态复制到下一状态中
     * 并将新滑块的上一状态指向本实例
     * 更新步数为本实例的步数+1
     *
     * @return 构造的新状态盒
     */
    private SlidingBox nextBoxFromCurrent() {
        SlidingBox nextSlidingBox = new SlidingBox();
        char[][] nextData = this.toMatrix();
        for (char[] nextDatum : nextData) {
            for (char c : nextDatum) {
                if (c == 0) {
                    Logger.warn("构造了不合法的下一步状态" + this.buildStateString(nextData));
                    Logger.warn("此时的状态" + this.stateString);
                }
            }
        }
        nextSlidingBox.buildBlocks(nextData);
        nextSlidingBox.setPrevSlidingBox(this);
        nextSlidingBox.setSteps(this.steps + 1);
        return nextSlidingBox;
    }

    /**
     * 判断状态数组是否完全相同
     *
     * @param anotherSlidingBox 待比较状态盒
     *
     * @return 判断结果，完全相同为true，存在不同元素为false
     */
    private boolean isIdenticalWith(SlidingBox anotherSlidingBox) {
        char[][] anotherData = anotherSlidingBox.getData();
        for (int i = 0; i < this.data.length; i++) {
            for (int j = 0; j < this.data[i].length; j++) {
                if (this.data[i][j] != anotherData[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 判断状态数组是否左右对称
     *
     * @param anotherSlidingBox 被比较的滑块盒
     *
     * @return 比较结果
     */
    private boolean isMirrorOf(SlidingBox anotherSlidingBox) {
        char[][] anotherData = anotherSlidingBox.getData();
        for (int i = 0; i < this.data.length; i++) {
            for (int j = 0; j < this.data[i].length; j++) {
                if (this.data[i][j] != anotherData[i][data[i].length - 1 - j]) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 判断两个滑块盒是否拥有相同布局
     *
     * @param anotherSlidingBox 被比较的滑块盒
     *
     * @return 比较结果
     */
    private boolean hasSameLayoutWith(SlidingBox anotherSlidingBox) {
        return this.blocks.values().stream()
                .flatMap(Collection::stream)//获取全部滑块
                .allMatch(block -> { //找到对应位置的滑块是否全部满足尺寸范围相同
                    int[] range = block.getRange();
                    Cell testCell = block.getCells().get(0);
                    Block targetBlock = anotherSlidingBox.findBlock(testCell.getRow(), testCell.getCol());
                    if (targetBlock == null) {
                        return false;
                    }
                    int[] targetRange = targetBlock.getRange();
                    //找到了对应滑块，先比较滑块的范围
                    boolean hasSameRange = range[0] == targetRange[0] &&
                            range[1] == targetRange[1] &&
                            range[2] == targetRange[2] &&
                            range[3] == targetRange[3];
                    //如果滑块的范围是相同的
                    if (hasSameRange) {
                        //再判断滑块编号，空白滑块对应空白滑块，非空滑块对应非空滑块，如此方可视为布局相等
                        return (block.getCode() == '0' && targetBlock.getCode() == '0') ||
                                (block.getCode() != '0' && targetBlock.getCode() != '0');
                    }
                    return false;
                });
    }

    /**
     * 根据位置查找网格
     *
     * @param row 行号
     * @param col 列号
     *
     * @return 查找到的网格
     */
    private Cell findCell(int row, int col) {
        final Cell[] resultCell = new Cell[1];
        this.blocks.forEach((code, blockList) -> blockList.forEach(block -> block.getCells().forEach(cell -> {
            //匹配位置相同的网格
            if (cell.getRow() == row && cell.getCol() == col) {
                resultCell[0] = cell;
            }
        })));
        return resultCell[0];
    }

    /**
     * 以数组形式输出修改后的滑块盒状态
     *
     * @return 网格编号数组
     */
    public char[][] toMatrix() {
        int rows = this.data.length,
                columns = this.data[0].length;
        char[][] matrix = new char[rows][columns];
        //逐次读取每个网格的数据
        this.blocks.forEach((code, blocks) -> blocks.forEach(block -> {
            block.getCells().forEach(cell -> matrix[cell.getRow()][cell.getCol()] = cell.getCode());
        }));

        return matrix;
    }

    /**
     * 把关卡数据转换成字符串表示
     *
     * @return 滑块盒数据的字符串表示
     */
    private String buildStateString(char[][] data) {
        StringBuilder stringBuilder = new StringBuilder("\n");
        for (char[] line : data) {
            for (char c : line) {
                stringBuilder.append(c);
            }
            stringBuilder.append("\n");
        }
        return stringBuilder.toString();
    }

    /**
     * 构建滑块盒模型
     * char[][] -> Blocks
     * char[][] -> stateString
     */
    public void buildBlocks(char[][] data) {
        this.data = data;
        //同步状态字符串
        this.stateString = this.buildStateString(data);
        //遍历puzzleData所有元素，构建滑块盒
        int rows = data.length, columns = data[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                char code = data[i][j];
                Cell cell = new Cell(i, j, code);
                Block block;
                List<Block> blockList;
                //如果尚未有本编号的滑块，则新建一个有本编号的滑块，再加入当前网格
                if (!this.blocks.containsKey(code)) {
                    blockList = new ArrayList<>();
                    block = new Block(cell);
                    blockList.add(block);
                    this.blocks.put(code, blockList);//注册这个新滑块
                } else {
                    //如果已经注册本编号的滑块，就把网格加入到滑块中
                    blockList = this.blocks.get(code);
                    //编号为0的网格单独成块
                    if (code == '0') {
                        block = new Block(cell);
                        blockList.add(block);
                    } else {
                        //编号不为0的滑块是唯一的，只须将网格接入它
                        block = blockList.get(0);
                        block.getCells().add(cell);
                    }
                }
            }
        }
        //空滑块编号为0
        this.emptyBlocks.addAll(this.blocks.get('0'));
        //主滑块编号为1
        this.primaryBlock = this.blocks.get('1').get(0);
    }

    public char[][] getData() {
        return data;
    }

    /**
     * 游戏是否胜利结束
     *
     * @return 主滑块是否到达指定地点
     */
    public boolean succeeded() {
        char[][] matrix = this.toMatrix();
        char primaryCode = this.primaryBlock.getCode();
        return matrix[3][1] == primaryCode &&
                matrix[4][1] == primaryCode &&
                matrix[3][2] == primaryCode &&
                matrix[4][2] == primaryCode;
    }

    /**
     * 散列值根据状态字符串生成
     *
     * @return 状态字符串得到的散列值
     */
    @Override
    public int hashCode() {
        return this.stateString.hashCode();
    }

    /**
     * 根据字符串判别是否相同，判断条件
     * 1.盒的状态是否完全与本盒相同
     * 2.盒的状态是否与本盒对称
     * 3.盒的滑块在相同的位置是不是一样大小
     *
     * @param o 初步比较对象
     *
     * @return 状态字符串比较的结果
     */
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        SlidingBox anotherSlidingBox = (SlidingBox) o;
        return this.isIdenticalWith(anotherSlidingBox) ||
                this.isMirrorOf(anotherSlidingBox) || this.hasSameLayoutWith(anotherSlidingBox);
    }

}
